package cn.bellychang.leetcode.question739;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ChangLiang
 * @date 2021/3/17
 */
public class Solution2 {

    public int[] dailyTemperatures(int[] T) {

        int[] result = new int[T.length];

        Deque<Integer> stack = new ArrayDeque<>(T.length);

        for (int i = 0; i < T.length; i++) {

            while (stack.size() != 0 && T[stack.peek()] < T[i]) {
                Integer index = stack.pop();

                // 这一步非常巧妙了 栈中存储的含义是第几天还没有找到大于其温度的天数 进来的是第i天
                // 两者之差就是间隔的天数
                result[index] = i - index;
            }
            stack.push(i);
        }
        return result;
    }
}
